package com.freetymekiyan.algorithms.level.easy;

/**
 * 299. Bulls and Cows
 * <p>
 * You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to
 * guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in
 * said guess match your secret number exactly in both digit and position (called "bulls") and how many digits match
 * the secret number but locate in the wrong position (called "cows"). Your friend will use successive guesses and
 * hints to eventually derive the secret number.
 * <p>
 * For example:
 * <p>
 * Secret number:  "1807"
 * Friend's guess: "7810"
 * Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.)
 * Write a function to return a hint according to the secret number and friend's guess, use A to indicate the bulls and
 * B to indicate the cows. In the above example, your function should return "1A3B".
 * <p>
 * Please note that both secret number and friend's guess may contain duplicate digits, for example:
 * <p>
 * Secret number:  "1123"
 * Friend's guess: "0111"
 * In this case, the 1st 1 in friend's guess is a bull, the 2nd or 3rd 1 is a cow, and your function should return
 * "1A1B".
 * You may assume that the secret number and your friend's guess only contain digits, and their lengths are always
 * equal.
 * <p>
 * Tags: Hash Table
 */
public class BullsAndCows {

  /**
   * Use an array of 10 digits as a simple table.
   * We can get # of bulls by comparing digits one by one.
   * If they are the same, # of bulls increase by 1.
   * Otherwise, we update the array by increasing count of digit in secret,
   * decreasing count of digit in guess.
   * We check count before update to get # of cows.
   */
  public String getHint(String secret, String guess) {
    int bulls = 0;
    int cows = 0;
    int[] count = new int[10];
    for (int i = 0; i < secret.length(); i++) {
      if (secret.charAt(i) == guess.charAt(i)) bulls++;
      else {
        /*
         * If count is less than zero before we increase it, it means that it was decreased by guess already.
         */
        if (count[secret.charAt(i) - '0']++ < 0) cows++;
        if (count[guess.charAt(i) - '0']-- > 0) cows++;
      }
    }
    return bulls + "A" + cows + "B";
  }
}
